package com.wdc.binarytree;

/**
 * Binary Search Tree 二叉搜索树
 * 泛型 key 版本
 */
public class BSTTree2<T extends Comparable<T>> {

    BSTNode<T> root; //根节点

    static class BSTNode<T> {

        T key;
        Object value;
        BSTNode<T> left;
        BSTNode<T> right;

        public BSTNode(T key) {
            this.key = key;
        }

        public BSTNode(T key, Object value) {
            this.key = key;
            this.value = value;
        }

        public BSTNode(T key, Object value, BSTNode<T> left, BSTNode<T> right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }


    /**
     * 查找关键字对应的值
     *
     * @param key 关键字
     * @return 关键字对应的值
     */
    public Object get(T key) {
        return doGet(root,key);
    }

    //封装递归函数
    private Object doGet(BSTNode<T> node, T key) {
        return null;
    }

    //非递归代码效率更高
    public Object getNoUse(T key){
        BSTNode<T> node = root;
        while( node != null ){
            /*
                返回 -1  说明 key < p.key
                     0  说明 key == p.key
                     1  说明 key > p.key
             */
            int res = key.compareTo(node.key);
            if (res < 0){
                node = node.left;
            }else if(res > 0 ) {
                node = node.right;
            }else {
                return node.value;
            }

        }
        return null;
    }





    /**
     * 查找最大关键字对应值
     *
     * @return
     */
    public Object max() {
        return null;
    }


    /**
     * 查找最小关键字对应值
     *
     * @return
     */
    public Object min() {
        return null;
    }

    /**
     * 查找关键字的前驱值
     *
     * @param key 关键字
     * @return 前驱值
     */
    public Object successor(T key) {
        return null;
    }


    /**
     * 查找关键字的后继值
     *
     * @param key 关键字
     * @return 后继值
     */
    public Object predecessor(T key) {
        return null;
    }

    /**
     * 根据关键字删除
     *
     * @param key 关键字
     * @return 被删除关键字对应的值
     */
    public Object delete(T key) {
        return null;
    }


}
